package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 斐波那契数
 * @date 2025/5/25 23:08
 */
public class Fib_509 {

    public static void main(String[] args) {
        Fib_509 fib509 = new Fib_509();

        System.out.println(fib509.fib(4));
    }

    /**
     * dmsxl-动态规划-状态压缩
     * <p>
     * 分析：
     * 因为dp[i]只依赖于前两个值，dp[i - 2] + dp[i - 1]，所以可不用数组维护
     */
    public int fib2(int n) {
        if (n < 2) return n;

        // 1.dp数组

        // 3.初始化
        // 状态压缩；因为dp[i]只依赖于前两个值，dp[i - 2] + dp[i - 1]，所以可不用数组维护
        int n1 = 0, n2 = 1, n3 = 0;
        // 4.遍历顺序
        for (int i = 2; i < n + 1; i++) {
            // 2.递推公式
//            dp[i] = dp[i - 2] + dp[i - 1];
            n3 = n1 + n2;
            // 更新n1、n2
            n1 = n2;
            n2 = n3;
            // 5.打印
        }
        return n3;
    }

    /**
     * 个解-动态规划
     */
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;

        // 1.dp数组，长度为n+1
        // dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        int[] dp = new int[n + 1];
        // 3.初始化
        dp[0] = 0;
        dp[1] = 1;
        // 4.遍历顺序
        // 因为dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，所以遍历的顺序一定是从前到后遍历的
        for (int i = 2; i < n + 1; i++) {
            // 2.递推公式
            dp[i] = dp[i - 2] + dp[i - 1];
            // 5.打印
            System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "dp[" + (i - 1) + "]=" + dp[i - 1]);
        }
        return dp[n];
    }

}
